|
In graph theory, the Möbius ladder ''M''''n'' is a cubic circulant graph with an even number ''n'' of vertices, formed from an ''n''-cycle by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is so-named because (with the exception of ''M''6 = ''K''3,3) ''M''''n'' has exactly ''n''/2 4-cycles which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by . == Properties == Every Möbius ladder is a nonplanar apex graph. Möbius ladders have crossing number one, and can be embedded without crossings on a torus or projective plane. Thus, they are examples of toroidal graphs. explores embeddings of these graphs onto higher genus surfaces. Möbius ladders are vertex-transitive but (again with the exception of ''M''6) not edge-transitive: each edge from the cycle from which the ladder is formed belongs to a single 4-cycle, while each rung belongs to two such cycles. When ''n'' ≡ 2 (mod 4), ''M''''n'' is bipartite. When ''n'' ≡ 0 (mod 4), by Brooks' theorem ''M''''n'' has chromatic number 3. show that the Möbius ladders are uniquely determined by their Tutte polynomials. The Möbius ladder ''M''8 has 392 spanning trees; it and ''M''6 have the most spanning trees among all cubic graphs with the same number of vertices.〔; .〕 However, the 10-vertex cubic graph with the most spanning trees is the Petersen graph, which is not a Möbius ladder. The Tutte polynomials of the Möbius ladders may be computed by a simple recurrence relation. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Möbius ladder」の詳細全文を読む スポンサード リンク
|